#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

int num = 0;
vector<int> memo;

// O(n) 级别算法 
// 递归自上而下 解决问题
int fib(int n){
	num++;
	if(n == 0) return 0;
	if(n == 1) return 1;

	// 每一个[n] 只会计算一次	
	if(memo[n] == -1){
	   memo[n] = fib(n - 1) + fib(n - 2);
	}

	return memo[n];
}


int main(){
	num = 0;
	int n = 1000;

	// 注意初始化
	memo = vector<int>(n + 1, -1);
	time_t startTime = clock();
	int res = fib(n);
	time_t endTime = clock();
	
	cout << "fib(" << n << ") = " << res << endl;
    cout << "time : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
    cout << "run function fib() " << num << " times." << endl;
}
